- Title
- Permutations of context-free, ET0L and indexed languages
- Creator
- Brough, Tara; Ciobanu, Laura; Elder, Murray; Zetzsche, Georg
- Relation
- Discrete Mathematics & Theoretical Computer Science Vol. 17, Issue 3, p. 167-178
- Relation
- https://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/viewArticle/2751.html
- Publisher
- Chapman & Hall
- Resource Type
- journal article
- Date
- 2016
- Description
- For a language L, we consider its cyclic closure, and more generally the language Ck(L), which consists of all words obtained by partitioning words from L into k factors and permuting them. We prove that the classes of ET0L and EDT0L languages are closed under the operators Ck. This both sharpens and generalises Brandstädt's result that if L is context-free then Ck(L) is context-sensitive and not context-free in general for k=3. We also show that the cyclic closure of an indexed language is indexed.
- Subject
- ET0L; EDT0L; indexed; context-free; cyclic closure
- Identifier
- http://hdl.handle.net/1959.13/1322811
- Identifier
- uon:24663
- Identifier
- ISSN:1462-7264
- Language
- eng
- Full Text
- Reviewed
- Hits: 4650
- Visitors: 4935
- Downloads: 332
| Thumbnail | File | Description | Size | Format | |||
|---|---|---|---|---|---|---|---|
| View Details Download | ATTACHMENT02 | Publisher version (open access) | 286 KB | Adobe Acrobat PDF | View Details Download |